package com.dy.数学.中级.分数到小数;

import java.util.HashMap;

/*
给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以字符串形式返回小数。

如果小数部分为循环小数，则将循环的部分括在括号内。

示例 1:

输入: numerator = 1, denominator = 2
输出: "0.5"
示例 2:

输入: numerator = 2, denominator = 1
输出: "2"
示例 3:

输入: numerator = 2, denominator = 3
输出: "0.(6)"
 */

/**
 * 整数部分很好处理，只要注意正负号的区分就行了，但是如何处理小数部分呢。如果只是简单的除法，
 * 那我们每次把余数乘以10，再除以被除数就可以得到当前位的小数了，得到新的余数，直到余数为0。
 * 难点在于，对于无尽循环小数，我们一直这么做永远也不能让余数变为0。这里我们可以用一个哈希表记录每次的余数，
 * 如果余数出现重复的时候，说明就产生循环了。为了能找出小数中循环的部分，
 * 我们在用哈希表时，还要把每个余数对应的小数位记录下来，这样子我们一旦遇到重复，就知道是从哪里开始循环的。
 */
public class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0 || denominator == 0) return "0";
        int sign = ((numerator < 0) ^ (denominator < 0)) ? -1 : 1;
        long num = numerator;
        long den = denominator;
        num = Math.abs(num);
        den = Math.abs(den);
        StringBuilder sb = new StringBuilder("");
        sb.append((sign == -1) ? "-" : "");
        sb.append(num / den);
        //map记录 余数和位置，frac记录商
        if (num % den != 0) {
            num = num % den;
            HashMap<Long, Integer> map = new HashMap<>();
            StringBuilder frac = new StringBuilder();
            int pos = 0;
            map.put(num, pos);

            while (num != 0) {
                num = num * 10;
                frac.append(num / den);

                num = num % den;

                if (map.containsKey(num)) {
                    //得到非循环部分
                    String pre = frac.substring(0, map.get(num));
                    //得到循环部分
                    String loop = frac.substring(map.get(num));
                    return sb.toString() + "." + pre + "(" + loop + ")";
                }
                pos++;
                map.put(num, pos);

            }
            return sb.toString() + "." + frac.toString();
        }
        return sb.toString();
    }
}
